\documentclass[twoside,a4paper]{ctexart}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{邵柯欣 (3200103310)}
\chead{Data Modeling homework 2}
\rhead{\today}

\section*{I. （3.2）利用例题3.2构造的kd树求解点$x = (3,4.5)^T$最近邻点．}

\subsection*{解：}
设$x_0$为$x$的当前最近邻点, $d$为当前最近邻点与$x$的距离．

首先寻找包含点$x = (3,4.5)$的叶节点：\\
$x^{(1)} = 3 < 7$,在节点的左边寻找;
$x^{(2)} = 4.5 > 4$,在节点的右边寻找;
$$x_0 = (4,7)^T \quad d = \sqrt(7.25).$$

验证父节点$(5,4)^T$: 
$\quad \sqrt(4.25) < d$
$$x_0 = (5,4)^T \quad d = \sqrt(4.25).$$

验证父节点的另一字节点$(2,3)^T$：
$\sqrt(3.25) < d$
$$x_0 = (2,3)^T \quad d = \sqrt(3.25).$$

验证父节点$(7,2)^T$:
$\sqrt(22.25) > d$

此时是根节点，所以最近邻点为$(2,3)^T$.

\section*{II. （3.３）参照算法３.３,写出输出为ｘ的ｋ近邻的算法.}

\subsection*{解：}
算法：\\
第一步：给定数据集Ｔ，随机取其中ｋ个点为ｘ的ｋ近邻，构成点集Ａ；\\
第二步：对Ａ中的所有点，关于到ｘ的距离从大到小排序，Ａ中第一个元素为ａ０，是Ａ中距离ｘ最远的点；\\
第三步：用点集Ｔ／Ａ构造平衡ｋｄ树，并用生成的ｋｄ树对ｘ进行最近邻搜索，寻找最近邻为ｘ０；\\
第四步：比较ｘ０和ａ０到ｘ的距离，\par
若ｘ０到ｘ的距离小于ａ０到ｘ的距离，互换ｘ０与ａ０，从第二步开始循环；\par
否则，结束并输出Ａ为ｘ的ｋ近邻．
\end{document}
